package demo.practice.linklist;

import demo.practice.ListNode;

import java.util.Stack;

public class P445 {
    /**
     * 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
     * <p>
     * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
     * 输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 8 -> 0 -> 7
     */


    public static void main(String[] args) {

        ListNode head= new ListNode(1);
        ListNode head2= new ListNode(9);
        head2.next= new ListNode(9);
//        head2.next.next= new ListNode(9);

//        ListNode head= new ListNode(7);
//        head.next=new ListNode(2);
//        head.next.next=new ListNode(4);
//        head.next.next.next=new ListNode(3);
//
//
//        ListNode head2= new ListNode(5);
//         head2.next= new ListNode(6);
//         head2.next.next= new ListNode(4);
//
         P445 p445= new P445();
         p445.addTwoNumbers(head,head2);
    }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;

        Stack<Integer> s1= new Stack<>();
        Stack<Integer> s2= new Stack<>();

        ListNode cur1=l1;
        ListNode cur2=l2;

        while (cur1!=null){
            s1.push(cur1.val);
            cur1=cur1.next;
        }

        while (cur2!=null){
            s2.push(cur2.val);
            cur2=cur2.next;
        }

        int pre= s1.peek()+s2.peek()>=10? 1:0;

        ListNode h=  new ListNode((s1.pop()+s2.pop())%10 );
        while (s1.size()>0 || s2.size()>0 ){
            ListNode prenode= new ListNode(( (s1.size()>0?s1.peek():0)+(s2.size()>0? s2.peek():0)+pre )%10);
            pre= ( (s1.size()>0?s1.pop():0)+(s2.size()>0? s2.pop():0)+pre )>=10 ? 1:0;
            prenode.next=h;
            h=prenode;
        }

        if(pre>0){
            ListNode prenode= new ListNode(pre);
            prenode.next=h;
            return prenode;
        }

        return h;



//        if(s1.size()==0 && s2.size()==0&& pre>0){
//            ListNode prenode= new ListNode(pre);
//            prenode.next=h;
//            return prenode;
//        }
//
//
//        if(s1.size()>0){
//            ListNode prenode= new ListNode(s1.pop());
//            prenode.next=h;
//            h=prenode;
//        }
//
//        if(s2.size()>0){
//            ListNode prenode= new ListNode(s2.pop());
//            prenode.next=h;
//            h=prenode;
//        }


//        return h;
    }
}
